Slide 5: Linear Structures: Queues (FIFO)

Queues: First-In, First-Out (FIFO) Structure

A Queue is a linear structure designed for sequential processing, adhering strictly to the FIFO principle: the element that has been in the queue the longest is the next to be removed.

Unlike Stacks (which use a single access point, the Top), Queues require two pointers:

Enqueue (Insertion): Elements are added to the Rear (or back).
Dequeue (Deletion): Elements are removed from the Front.

This structure guarantees that the order of processing strictly matches the order of arrival, essential for scheduling and buffering applications.

Queue Operation Complexity

Operation	Description	Time $T(N)$	Space $S(N)$
Enqueue	Insert at rear	$O(1)$	$O(1)$
Dequeue	Remove from front	$O(1)$	$O(1)$
Peek	View front element	$O(1)$	$O(1)$
Search	Find element	$O(N)$	$O(1)$

Note: $O(1)$ complexity is maintained by using a Linked List or a Circular Array implementation.

📝 Interactive Quiz

1. A queue holds [A, B, C] (front to rear). 'D' is Enqueued, then one element is Dequeued. What is the final state?

A) [B, C, D]
B) [A, B, C]
C) [D, A, B]
D) [C, D]

2. What is the time complexity of the `Enqueue` operation in an efficiently implemented queue?

A) $O(1)$
B) $O(\log N)$
C) $O(N)$
D) $O(N \log N)$

3. Which graph traversal algorithm fundamentally relies on a queue?

A) Depth-First Search (DFS)
B) Breadth-First Search (BFS)
C) A* Search
D) Recursive Tree Traversal

4. Why can a simple array be inefficient for a queue's `Dequeue` operation?

A) It uses too much memory.
B) It violates the FIFO principle.
C) Shifting all remaining elements takes $O(N)$ time.
D) It's impossible to implement.

KEY TIPS

💡 Key Tips

Graph Traversal (BFS)

Queues are the core mechanism for Breadth-First Search (BFS), ensuring all nodes at the current depth level are visited before moving to the next level. This contrasts with Stacks, which drive Depth-First Search (DFS).

Resource Management

In operating systems, queues manage critical resources:

CPU Scheduling: Processes waiting for the CPU are handled in queues.
I/O Buffering: Handling requests in the order they arrive (e.g., printing).

Implementation Insight

While a simple array might require $O(N)$ time to shift elements during Dequeue, efficient queues use Circular Arrays or Doubly Linked Lists for guaranteed $O(1)$ performance.